"""
算法思想：非递归版本的归并排序，通过迭代方式按子数组长度逐步合并。初始子数组长度为 1，每次合并相邻的两个子数组，然后将子数组长度翻倍，直至整个数组有序。

代码解释：
迭代合并：外层循环控制子数组长度length（从 1 开始，每次翻倍），内层循环遍历所有相邻的子数组对。
边界处理：计算子数组边界时使用min函数防止越界，仅当右子数组存在时才进行合并。
merge 函数：与递归版本类似，但直接操作原数组的指定区间，通过临时数组存储合并结果后写回原数组。
时间复杂度与递归版本相同（O(nlogn)），空间复杂度为O(n)（临时数组），但避免了递归调用的栈开销。
"""


def two_way_merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr.copy()  # 拷贝避免修改原数组

    # 子数组长度从1开始，每次翻倍
    length = 1
    while length < n:
        # 遍历所有子数组对
        for i in range(0, n, 2 * length):
            # 左子数组的起始和结束索引
            left_start = i
            left_end = i + length - 1
            # 右子数组的起始和结束索引（防止越界）
            right_start = i + length
            right_end = min(i + 2 * length - 1, n - 1)

            # 若右子数组存在，进行合并
            if right_start <= n - 1:
                merge(arr, left_start, left_end, right_start, right_end)

        # 子数组长度翻倍
        length *= 2

    return arr


def merge(arr, left_start, left_end, right_start, right_end):
    """合并数组中[left_start, left_end]和[right_start, right_end]两个有序子数组"""
    # 临时数组存储合并结果
    temp = []
    i = left_start  # 左子数组指针
    j = right_start  # 右子数组指针

    # 比较并合并元素
    while i <= left_end and j <= right_end:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1

    # 处理剩余元素
    while i <= left_end:
        temp.append(arr[i])
        i += 1
    while j <= right_end:
        temp.append(arr[j])
        j += 1

    # 将合并结果写回原数组
    arr[left_start:right_end + 1] = temp


# 测试
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = two_way_merge_sort(arr)
print("二路归并排序结果:", sorted_arr)  # 输出: [5, 6, 7, 11, 12, 13]


